// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.red;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import static junit.framework.Assert.assertEquals;
import static junit.framework.Assert.assertTrue;


// TODO: больше one-pass тестов, fail-тестов и совпадение не с начала строки.
// множественные ветвления


public class NfaInterpreterTest {
  @Before
  public void setUp() {}

  @After
  public void tearDown() {}

  @Test
  public void backtrackerMustDie() {
    final StringBuilder pattern_sb = new StringBuilder();
    final StringBuilder string_sb = new StringBuilder();
    for ( int i = 0 ; i != 1000 ; i++ ) {
      pattern_sb.append("a+");
      string_sb.append("a");
    }

    setPatternAndString(pattern_sb.toString(), string_sb.toString());
    assertEquals(string_sb.toString(), submatch(0));
  }

   @Test
  public void emptyStringAndPattern() {
    setPatternAndString("()", "");
    assertEquals("", submatch(1));
  }

  @Test
  public void simpleOneSubmatch() {
    setPatternAndString("a(bc)", "abcxyz");
    assertEquals("bc", submatch(1));
  }

  @Test
  public void simpleTwoSubmatches() {
    setPatternAndString("a(bc)(xy)z", "abcxyz");
    assertEquals("bc", submatch(1));
    assertEquals("xy", submatch(2));
  }

  @Test
  public void twoSubmatchesWithFork() {
    setPatternAndString("(ab+)(cd)", "abcd");
    assertEquals("ab", submatch(1));
    assertEquals("cd", submatch(2));

    setPatternAndString("(ab+)(cd*)", "abbc");
    assertEquals("abb", submatch(1));
    assertEquals("c", submatch(2));

    setPatternAndString("(ab+)(cd?)", "abbc");
    assertEquals("abb", submatch(1));
    assertEquals("c", submatch(2));

    setPatternAndString("(ab+)(cd?)", "abbcdd");
    assertEquals("abb", submatch(1));
    assertEquals("cd", submatch(2));
  }

  @Test
  public void twoSubmatchesWithForkAndCollision() {
    setPatternAndString("(ab+)(bcd)", "abcd");
    assertTrue(noMatch());

    setPatternAndString("(ab+)(bcd)", "abbcd");
    assertEquals("ab", submatch(1));
    assertEquals("bcd", submatch(2));
  }

  @Test
  public void coveringSubmatch() {
    setPatternAndString("((a)(b))", "aby");
    assertEquals("ab", submatch(1));
    assertEquals("a", submatch(2));
    assertEquals("b", submatch(3));
  }

  @Test
  public void differingSaveSemantics() {
    setPatternAndString("(a+)", "aaa");
    assertEquals("aaa", submatch(1));

    setPatternAndString("(a)+", "aaa");
    assertEquals("a", submatch(1));

    setPatternAndString("(a|b)+", "baaa");
    assertEquals("a", submatch(1));

    setPatternAndString("(a|b)+", "abab");
    assertEquals("abab", submatch(0));
    assertEquals("b", submatch(1));

    setPatternAndString("((?:a|b)+)", "abab");
    assertEquals("abab", submatch(1));
  }

  @Test
  public void simpleAlternative() {
    setPatternAndString("(a|b)", "cbax");
    assertEquals("b", submatch(1));
  }

  @Test
  public void alternative() {
    setPatternAndString("((a|b)+)", "ababbb");
    assertEquals("ababbb", submatch(1));

    setPatternAndString("((a|b)+)$", "ababbb");
    assertEquals("ababbb", submatch(1));

    setPatternAndString("(^(a)|(b)$)c", "acd");
    assertEquals("a", submatch(1));
    assertEquals("a", submatch(2));
    assertEquals("", submatch(3));

    setPatternAndString("((a)|(b))c", "bc");
    assertEquals("b", submatch(1));
    assertEquals("", submatch(2));
    assertEquals("b", submatch(3));
  }

  @Test
  public void bigAlternative() {
    setPatternAndString("(((a)|(b)|(c)|(d))+)", "ababbbcd");
    assertEquals("ababbbcd", submatch(1));
    assertEquals("d", submatch(2));
    assertEquals("a", submatch(3));
    assertEquals("b", submatch(4));
    assertEquals("c", submatch(5));
    assertEquals("d", submatch(6));

  }

  @Test
  public void skipSave() {
    setPatternAndString("^(^|(^))a$", "a");
    assertEquals("", submatch(1));
    assertEquals("", submatch(2));
  }


  @Test
  public void lazyOneOrMore() {
    setPatternAndString("(a+)", "aaaa");
    assertEquals("aaaa", submatch(1));

    setPatternAndString("(a+?)", "aaaa");
    assertEquals("a", submatch(1));
  }

  @Test
  public void lazyZeroOrMany() {
    setPatternAndString("(a*)", "aaaa");
    assertEquals("aaaa", submatch(1));

    setPatternAndString("(a*?)", "aaaa");
    assertEquals("", submatch(1));
  }

  @Test
  public void lazyZeroOrOne() {
    setPatternAndString("(a?)", "aaaa");
    assertEquals("a", submatch(1));

    setPatternAndString("(a??)", "aaaa");
    assertEquals("", submatch(1));
  }


  @Test
  public void noneOnePass() {
    setPatternAndString("(x*)x", "xxx");
    assertEquals("xx", submatch(1));

    setPatternAndString("(\\d+).(\\d+)", "12345");
    assertEquals("123", submatch(1));
    assertEquals("5", submatch(2));

    setPatternAndString("(.*)x(.*)", "abcx");
    assertEquals("abc", submatch(1));
    assertEquals("", submatch(2));

    setPatternAndString("(.*)x(.*)", "abcxx");
    assertEquals("abcx", submatch(1));
    assertEquals("", submatch(2));

    setPatternAndString("(.*)x(.*)", "abcxxy");
    assertEquals("abcx", submatch(1));
    assertEquals("y", submatch(2));
  }

  @Test
  public void noneOnePassAlternative() {
    setPatternAndString("(xy|xz)", "xzy");
    assertEquals("xz", submatch(1));

    setPatternAndString("((xy|xz)*)", "xzxy");
    assertEquals("xzxy", submatch(1));
    assertEquals("xy", submatch(2));
  }

  @Test
  public void onePass() {
    setPatternAndString("(x*y+)y(x*)", "xxyy");
    assertEquals("xxy", submatch(1));
    assertEquals("", submatch(2));

    setPatternAndString("x(y|z)", "xzy");
    assertEquals("z", submatch(1));

    setPatternAndString("(\\d+)-(\\d+)", "12-1");
    assertEquals("12", submatch(1));
    assertEquals("1", submatch(2));
  }


  @Test
  public void anchors() {
    setPatternAndString("(^)*", "");
    assertEquals("", submatch(1));

    setPatternAndString("(^)*", "a");
    assertEquals("", submatch(1));

    setPatternAndString("(^|$)?", "");
    assertEquals("", submatch(1));

    setPatternAndString("(^|$)*?", "xxyy");
    assertEquals("", submatch(1)); // TODO

    setPatternAndString("(^|$)*", "xxyy");
    assertEquals("", submatch(1));

    setPatternAndString("(^|$)+", "");
    assertEquals("", submatch(1));

    setPatternAndString("(^|$)+", "xxyy");
    assertEquals("", submatch(1));
  }


  private void setPatternAndString(final String pattern, final String string) {
    regex_ = new Regex(pattern);
    string_ = string;
    submatches_ = regex_.search(string);
  }

  private String submatch(final int id) {
    return submatches_[id].toString();
  }

  private boolean noMatch() {
    return submatches_ == null;
  }

  private Regex regex_;
  private String string_;
  private Submatch[] submatches_;
}
